home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _polygon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  6.7 KB  |  330 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _polygon.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/polygon.h>
  18. #include <LEDA/sweep_segments.h>
  19. #include <math.h>
  20.  
  21.  
  22. //------------------------------------------------------------------------------
  23. // polygons
  24. //------------------------------------------------------------------------------
  25.  
  26.  
  27. polygon::polygon()  { PTR = new polygon_rep; }
  28.  
  29.  
  30. ostream& operator<<(ostream& out, const polygon& p) 
  31. { p.vertices().print(out);
  32.   return out;
  33.  } 
  34.  
  35. istream& operator>>(istream& in,  polygon& p) 
  36. { list<point> L; 
  37.   L.read(in); 
  38.   p = polygon(L); 
  39.   return in;
  40. }
  41.  
  42.  
  43. static void polygon_check(const list<segment>&);
  44.  
  45. polygon::polygon(const list<point>& pl, bool check)
  46. { PTR = new polygon_rep;
  47.  
  48.   list_item it,it1;
  49.  
  50.   forall_list_items(it,pl)
  51.   { it1 = pl.cyclic_succ(it);
  52.     ptr()->seg_list.append(segment(pl[it],pl[it1]));
  53.    }
  54.  
  55.   if (check) polygon_check(ptr()->seg_list);
  56. }
  57.  
  58. list<point> polygon::vertices() const
  59. { list<point> result;
  60.   segment s;
  61.   forall(s,ptr()->seg_list) result.append(s.start());
  62.   return result;
  63. }
  64.  
  65.  
  66.  
  67.  
  68. static void polygon_check(const list<segment>& seg_list)
  69. {  if (seg_list.length() < 3) 
  70.      error_handler(1,"polygon: must be simple");
  71.  
  72.    list<point> L;
  73.    SWEEP_SEGMENTS(seg_list,L);
  74.  
  75.   if (L.length() != seg_list.length())
  76.    error_handler(1,"polygon: must be simple");
  77.  
  78.   list_item it;
  79.  
  80.   double angle = 0;
  81.  
  82.   forall_list_items(it,seg_list)
  83.   { list_item succ = seg_list.cyclic_succ(it);
  84.     segment s1 = seg_list[it];
  85.     segment s2 = seg_list[succ];
  86.     angle += s1.angle(s2);
  87.    }
  88.  
  89.   if (angle > 0)
  90.    error_handler(1,"polygon: point list must be clockwise oriented.");
  91. }
  92.  
  93. polygon polygon::translate(double alpha, double d) const
  94. { list<point> L;
  95.   segment s;
  96.   forall(s,ptr()->seg_list) L.append(s.start().translate(alpha,d));
  97.   return polygon(L,false);
  98. }
  99.  
  100. polygon polygon::translate(const vector& v) const
  101. { list<point> L;
  102.   segment s;
  103.   forall(s,ptr()->seg_list) L.append(s.start().translate(v));
  104.   return polygon(L,false);
  105. }
  106.  
  107. polygon polygon::rotate(const point& origin, double alpha) const
  108. { list<point> L;
  109.   segment s;
  110.   forall(s,ptr()->seg_list) L.append(s.start().rotate(origin,alpha));
  111.   return polygon(L,false);
  112. }
  113.  
  114. polygon polygon::rotate(double alpha) const
  115. { return rotate(point(0,0),alpha);
  116.  }
  117.  
  118.  
  119.  
  120. bool polygon::inside(const point& p) const
  121. {
  122.   line l(p,M_PI_2);  // vertical line through p
  123.  
  124.   int count = 0;
  125.  
  126.   segment s;
  127.   forall(s,ptr()->seg_list)
  128.   { point q;
  129.     if (!l.intersection(s,q)) continue;
  130.     if (q.ycoord() < p.ycoord()) continue;
  131.     if (q == s.start())  continue;
  132.     if (q == s.end())  continue;
  133.     count++ ;
  134.    }
  135.  
  136.   list<point> plist = vertices();
  137.  
  138.   list_item i0 = plist.first();
  139.  
  140.   while (plist[i0].xcoord() == p.xcoord())  i0 = plist.cyclic_pred(i0);
  141.  
  142.   list_item i = plist.cyclic_succ(i0);
  143.  
  144.   for(;;)
  145.   { 
  146.     while ( i != i0 && (plist[i].xcoord() != p.xcoord() || 
  147.                         plist[i].ycoord() < p.ycoord()    )  )
  148.        i = plist.cyclic_succ(i);
  149.  
  150.     if (i==i0) break;
  151.  
  152.     point q  = plist[i];
  153.     point q0 = plist[plist.cyclic_pred(i)];
  154.  
  155.     while ((plist[i].xcoord()==p.xcoord()) && (plist[i].ycoord() >= p.ycoord()))
  156.     { if (plist[i]==p) return true;
  157.       i = plist.cyclic_succ(i);
  158.      }
  159.  
  160.     point q1 = plist[i];
  161.  
  162.      if (q0.xcoord() < p.xcoord() && q1.xcoord() > p.xcoord()) count++;
  163.       if (q0.xcoord() > p.xcoord() && q1.xcoord() < p.xcoord()) count++;
  164.  
  165.    }
  166.  
  167.    return count%2;
  168.  
  169. }
  170.  
  171.  
  172.  
  173. bool polygon::outside(const point& p) const { return !inside(p); }
  174.  
  175.  
  176.  
  177. list<point> polygon::intersection(const segment& s) const
  178. { list<point> result;
  179.   segment t;
  180.   point p;
  181.  
  182.   forall(t,ptr()->seg_list) 
  183.     if (s.intersection(t,p))
  184.      if (result.empty()) result.append(p);
  185.      else if (p != result.tail() ) result.append(p);
  186.  
  187.   return result;
  188. }
  189.  
  190.  
  191. list<point> polygon::intersection(const line& l) const
  192. { list<point> result;
  193.   segment t;
  194.   point p;
  195.  
  196.   forall(t,ptr()->seg_list) 
  197.     if (l.intersection(t,p))
  198.      if (result.empty()) result.append(p);
  199.      else if (p != result.tail() ) result.append(p);
  200.  
  201.   return result;
  202. }
  203.  
  204.  
  205. // intersection with polygon
  206.  
  207. static bool polygon_test_edge(GRAPH<point,int>& G,edge& i1)
  208. { node v = G.target(i1);
  209.  
  210.   edge e,i2=nil,o1=nil,o2=nil;
  211.  
  212.   forall_adj_edges(e,v)
  213.     if (e != i1)
  214.     { if (v==target(e)) i2 = e;
  215.       else if (G[e]== G[i1]) o1 = e;
  216.            else o2 = e;
  217.      }
  218.  
  219.   if (i2==nil) return false;
  220.  
  221.   segment si1(G[source(i1)],G[v]);
  222.   segment si2(G[v],G[source(i2)]);
  223.   segment so2(G[v],G[target(o2)]);
  224.  
  225.   double alpha = si1.angle(si2);
  226.   double beta  = si1.angle(so2);
  227.  
  228.   return (alpha > beta);
  229.  
  230. }
  231.  
  232.  
  233.  
  234. static edge polygon_switch_edge(GRAPH<point,int>& G,edge i1)
  235. { node v = G.target(i1);
  236.  
  237.   edge e,i2=nil,o1=nil,o2=nil;
  238.  
  239.   forall_adj_edges(e,v)
  240.     if (e != i1)
  241.     { if (v==target(e)) i2 = e;
  242.       else if (G[e]== G[i1]) o1 = e;
  243.            else o2 = e;
  244.      }
  245.  
  246.   if (i2==nil) return  o1;
  247.  
  248.   segment si1(G[source(i1)],G[v]);
  249.   segment si2(G[v],G[source(i2)]);
  250.   segment so1(G[v],G[target(o1)]);
  251.   segment so2(G[v],G[target(o2)]);
  252.  
  253.   double alpha = si1.angle(si2);
  254.   double beta  = si1.angle(so2);
  255.   double gamma = si1.angle(so1);
  256.  
  257.   if (alpha < beta) cout << "error: alpa < beta!!\n";
  258.  
  259.   if (gamma >= beta) return o2;
  260.   else return o1;
  261.  
  262. }
  263.  
  264.  
  265. list_polygon_ polygon::intersection(const polygon& P) const
  266. {
  267.  
  268.   list<polygon> result;
  269.  
  270.   GRAPH<point,int> SUB;
  271.  
  272.   SWEEP_SEGMENTS(segments(),P.segments(),SUB);
  273.  
  274.   int N = SUB.number_of_nodes();
  275.  
  276.   if (N < size() + P.size())
  277.    error_handler(1,"polygon: sorry, internal error in intersection");
  278.  
  279.   if (N == size() + P.size())
  280.   { // no intersections between edges of (*this) and P
  281.     // check for inclusion
  282.  
  283.     segment s1 = ptr()->seg_list.head();
  284.     segment s2 = P.ptr()->seg_list.head();
  285.     point   p1 = s1.start();
  286.     point   p2 = s2.start();
  287.  
  288.     if (P.inside(p1))                     // (*this) is conained in P
  289.       result.append(*this);
  290.     else
  291.       if (inside(p2))                     // P is conained in (*this)
  292.         result.append(P);                   
  293.  
  294.  
  295.     return result;
  296.  
  297.    }
  298.  
  299.   SUB.make_undirected();
  300.  
  301.   edge e;
  302.  
  303.   list<point> PL;
  304.  
  305.   edge_array<bool> marked(SUB,false);
  306.  
  307.   forall_edges(e,SUB) 
  308.   { edge f;
  309.     if (!marked[e]  && SUB.outdeg(target(e))>1) 
  310.       if (polygon_test_edge(SUB,e))
  311.       { // new polygon found
  312.        marked[e] = true;
  313.        PL.append(SUB[source(e)]);
  314.        f = polygon_switch_edge(SUB,e);
  315.        while (f!=e)
  316.        { marked[f] = true;
  317.          PL.append(SUB[source(f)]);
  318.          f = polygon_switch_edge(SUB,f);
  319.         }
  320.        result.append(polygon(PL,false));
  321.        PL.clear();
  322.       }
  323.   }
  324.  
  325.  SUB.make_directed();
  326.  
  327.  return result;
  328.  
  329. }
  330.